Communication systems having multiple nodes transmit and receive data over communication links. In many systems, a communication node is capable of communicating with multiple other nodes. Nodes that communicate directly with each other over a communication link are referred to herein as "neighboring nodes".
Commonly, a data packet intended to be transmitted from a source terminal to a destination terminal is routed through the system using routing tables stored in each node. A communication node identities the destination of the data packet and determines, using the routing tables, to which neighboring node the data packet should be sent so that the packet may ultimately reach its destination.
A system which has many nodes may wish to balance the traffic loads over all available links when multiple possible routes exist between a source and a destination of a data packet. Prior art routing table configurations do not provide an inherent ability to balance loads by distributing data packets among the multiple possible routes.
A data packet may contain different types of data (e.g., information, test, telemetry, system operations data). Although the data packets may need to be routed differently based on their packet type, prior art systems cannot perform discretionary routing using only the current routing table configurations. An example of the inability of prior art systems simply to differentially handle different types of data packets occurs when a new node is brought into the system.
When a new node is brought into the communication system, neighboring nodes must alter their routing strategy to recognize the new node. Prior art methods require the neighboring nodes to load new tables that recognize the new node. Generating and loading new routing tables is time consuming, and synchronizing usage of the new tables is difficult. Loading time and synchronization problems increase as the number of neighboring nodes increases. Additionally, routing tables often are of considerable size, and sending new routing tables to each neighboring node uses a significant quantity of valuable system bandwidth which could better be utilized for revenue-producing data.
Nodes being added to a system should be tested before they are used to support all types of data. Additionally, a system may occasionally test a pre-existing node to verify that it is operating according to system specifications. A problem with prior art systems is that they do not embody simple methods of testing a new or pre-existing node (referred to herein as a "node-under-test") and then synchronizing neighboring nodes' recognition of the node's full operational status. To test a node, prior art methods interrupt system operations to route test data packets through the node-under-test using a set of routing tables designed for test data only. After testing is completed, new routing tables must be loaded into neighboring nodes, resulting in several of the problems discussed above.
Other prior art methods may have different routing tables: some tables used for test data and other tables used for other types of data. Because routing tables often use large blocks of memory, multiple routing tables are undesirable because they increase the quantity of memory a node requires. Prior art systems also have the same synchronization problems in transitioning from a testing phase of operation to full operations.
Besides adding and testing a new or pre-existing node, a node may be purposefully withdrawn from the system, or may become incapable of operating because of a failure, for example. Similar to adding a new node to the system, prior art methods may load new tables into the neighboring nodes so that the neighboring nodes will not route data to the withdrawn node. However, table generation and loading is time consuming. Additionally, by using prior an methods, data may be lost during table generation and loading because neighboring nodes may continue to route data to a failed node as if it were still capable of operating.
What are needed are a method and apparatus to balance traffic loads among the multiple possible routes using a single routing table. Further needed are a method and apparatus to differentially route a data packet based on its type. Further needed are a method and apparatus to synchronize routing among neighboring nodes during insertion, test, or removal of a communication node without disruption to the communication system. Further needed are a method and apparatus to synchronize routing modifications for multiple nodes in a timely manner and without using a significant amount of system bandwidth.